# -*- coding:utf-8 -*-
from functools import lru_cache
import time


def fib(number: int) -> int:  # 递归40次
    if number == 0:
        return 0
    if number == 1:
        return 1
    return fib(number - 1) + fib(number - 2)


def fib2(number: int) -> int:  # 最大值
    a, b = 0, 1
    while a < number:
        print(a, end=' ')
        a, b = b, a + b
    return a


@lru_cache
def fib_memoization(number: int) -> int:  # 缓存递归40次
    if number == 0:
        return 0
    if number == 1:
        return 1
    return fib_memoization(number - 1) + fib_memoization(number - 2)


start = time.time()
print(fib_memoization(40))

print(f'Duration:{time.time() - start}s')
